import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/11 21:28
 */
// 二叉树最大宽度
    // https://leetcode.cn/problems/maximum-width-of-binary-tree/
    // BFS
    // 问题在null也算，也就是视作满二叉树
public class Solution662 {
    int maxWidth = 1;
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        // 层序遍历队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // 索引记录队列
        LinkedList<Integer> indexList = new LinkedList<Integer>();
        queue.offer(root);
        indexList.add(1);
        // 使用size变量跟踪当层节点数量
        int size = 1;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            size--;
            Integer i = indexList.removeFirst();
            if (poll.left!=null) {
                queue.add(poll.left);
                // 记录该节点左子节点索引
                indexList.add(2*i);
            }
            if (poll.right!=null) {
                queue.add(poll.right);
                indexList.add(2*i+1);
            }
            if (size==0) {
                if (indexList.size() >= 2) {
                    maxWidth = Math.max(maxWidth, indexList.getLast() - indexList.getFirst() + 1);
                }
                size = queue.size();
            }
        }
        return maxWidth;
    }
}
